#include "CarStop.h"
#include <iostream>

// 两个栈实现一个队列
class MyQueue
{
    using ElementType = DoubleLinkList::ElementType;

public:
    void Push(const ElementType &element)
    {
        while (s2.IsEmpty() == false)
        {
            s1.Push(*s2.GetTop());
            s2.Pop();
        }
        s1.Push(element);
    }
    void Pop()
    {
        while (s1.IsEmpty() == false)
        {
            s2.Push(*s1.GetTop()); // 先把s1全扔在s2，再把s2出栈
            s1.Pop();
        }
        s2.Pop();
    }
    ElementType *GetFront()
    {
        while (s1.IsEmpty() == false)
        {
            s2.Push(*s1.GetTop());
            s1.Pop();
        }
        return &s2.GetTop();
    }
    bool IsEmpty()
    {
        return s1.IsEmpty() && s2.IsEmpty();
    }

private:
    LinkStack s1;
    LinkStack s2;
};

// 两个队列实现一个栈
class MyStack
{
    using ElementType = DoubleLinkList::ElementType;

public:
    void Push(const ElementType &element)
    {
        while (q2.IsEmpty() == false)
        {
            q1.Push(*q2.GetFront());
            q2.Pop();
        }
        q1.Push(element);
    }
    void Pop()
    {
        while (q1.Size() > 1) // 留一个，前面的导到q2中，然后再将剩下的一个导出去
        {
            q2.Push(*q1.GetFront());
            q1.Pop();
        }
        q1.Pop();    
        while (q2.IsEmpty() == false)   // Pop掉之后需要再给导回去   // 因为这个是Pop后的，所以可以直接将剩下的元素给直接导回去
        {
            q1.Push(*q2.GetFront());
            q2.Pop();
        }
    }
    ElementType *GetTop()
    {
        while (q1.Size() > 1)
        {
            q2.Push(*q1.GetFront());
            q1.Pop();
        }
        long r = (long)*q1.GetFront(); // 取出来最后进入的数据(后进先出)

        q2.Push(*q1.GetFront());       // 因为如果不先把q1中的数据全取出来，再插入便会打乱顺序；
        q1.Pop();                      

        while (q2.IsEmpty() == false)   // 始终保证只有q1中的有数据
        {
            q1.Push(*q2.GetFront());
            q2.Pop();
        }
        return (ElementType *)r;
    }
    bool IsEmpty()
    {
        return q1.IsEmpty() && q2.IsEmpty();
    }
private:
    LinkQueue q1;
    LinkQueue q2;
};

int main()
{
    MyQueue q;
    // MyStack q;
    for (long i = 1; i <= 10; i++)
    {
        q.Push((void *)i);
    }
    while (q.IsEmpty() == false)
    {
        // std::cout << (long)*q.GetFront() << " ";
        std::cout << (long)q.GetTop() << " ";
        q.Pop();
    }
    std::cout << std::endl;
    return 0;
}
